import java.util.Arrays;
import java.util.Stack;

//链栈
public class LinkedStack {
    //栈的特性是只对最后一个入栈的方法操作
    //所以 使用链表结构时，每个节点要记住上一个节点 而不是下一个
    Integer value;

    LinkedStack prev;

    public LinkedStack(int value) {
        this.value = value;
        this.prev = null;
    }
    public LinkedStack(int value, LinkedStack prev) {
        this.value = value;
        this.prev = prev;
    }

    //入栈
    public void push(int value){
        this.prev = new LinkedStack(this.value, this.prev);
        this.value = value;
    }
    //出栈
    public int pop() throws Exception {
        if(this.value != null){
            int i = this.value;
            if(this.prev != null){
                this.value=this.prev.value;
                this.prev=this.prev.prev;
            }else {
                this.value = null;
            }
            return i;
        }else {
            throw new Exception("The Stack has been null");
        }
    }
    //查看栈顶
    public int peek() throws Exception {
        if(this.value != null){
            return this.value;
        }else {
            throw new Exception("The Stack has been null");
        }
    }

    public static void main(String[] args) throws Exception {
        //建立一个链栈
        LinkedStack linkedStack = new LinkedStack(1);
        linkedStack.push(2);
        linkedStack.push(3);
        linkedStack.push(4);
        //看一下栈顶
        System.out.println(linkedStack.peek()); //输出4 成功
        //出栈
        linkedStack.pop();
        System.out.println(linkedStack.peek()); //输出3 成功
        //测试一直出栈的异常
        linkedStack.pop(); //此时栈中还剩 1 2
        linkedStack.pop(); //此时栈中还剩 1
        linkedStack.pop(); //此时栈已空
        System.out.println(linkedStack.peek()); //查看栈顶 报错 成功
    }
}

class Solution {
    public int evalRPN(String[] tokens){
        Stack<String> stack = new Stack<>();
        for (String token : tokens) {
            stack.push(token);
        }
        return step(stack);
    }
    public int step(Stack<String> stack) {
        Integer a,b,c ;
        String pop1 = stack.pop();
        switch (pop1) {
            case "+" -> {
                a = step(stack);
                b = step(stack);
                c = b + a;
            }
            case "-" -> {
                a = step(stack);
                b = step(stack);
                c = b - a;
            }
            case "*" -> {
                a = step(stack);
                b = step(stack);
                c = b * a;
            }
            case "/" -> {
                a = step(stack);
                b = step(stack);
                c = b / a;
            }
            default ->
                    c = Integer.parseInt(pop1);
        }
        return c;
    }
}
